package top.humbleyuan.dp;

import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:15
 * @Des 不同路径 II(有障碍)
 */
public class LeetCode_63 {
    public static void main(String[] args) {
        int[][] mn = new int[][]{{0,0,0,1},{0,0,1,0},{0,0,0,0}};

        int[] d = new int[mn[0].length];
        // 先确定第一行
        for(int i = 0;i < mn[0].length;i++) {
            if(mn[0][i] == 1) {
                Arrays.fill(d,i,mn[0].length,0);
                break;
            }
            d[i] = 1;
        }

        // 从第二行开始
        for(int i = 1;i < mn.length;i++) {
            for(int j = 0;j < mn[i].length;j++) {
                if (j > 0 && (d[j] == 0 && d[j-1] == 0))
                    break;
                d[j] = mn[i][j] == 1 ? 0 : (j == 0 ? 0 : d[j-1]) + d[j];
            }
        }

        System.out.println(d[mn[0].length-1]);
    }
}
